﻿#pragma warning(disable: 4996)
#pragma warning(disable: 6031)

/*
这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，111111就可以被13整除。 现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算，输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。

提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 —— 比如，程序输入31，那么就输出3584229390681和15，因为31乘以3584229390681的结果是111111111111111，一共15个1。

输入格式：
输入在一行中给出一个不以5结尾的正奇数x（<1000）。

输出格式：
在一行中输出相应的最小的s和n，其间以1个空格分隔。

输入样例：
31
输出样例：
3584229390681 15
*/

#include <stdio.h>
#include <math.h>

struct LargeInt {
	int n2;
	int n;
	int a[50000];
};

const int N = 5;
const int VN = 100000;

struct LargeInt* product_ten(struct LargeInt* a)
{
	a->n2 = (a->n++) / N;
	a->a[a->n2] = a->a[a->n2] * 10 + 1;
	return a;
}

int li_mod(struct LargeInt* a, int n, struct LargeInt* b)
{
	int h = 0;
	b->n2 = a->n2;
	for (int i = a->n2; i >= 0; i--)
	{
		int k = a->a[i] + h * VN;
		h = (k) % n;
		b->a[i] = k / n;
	}
	return h;
}

void li_dump(struct LargeInt* a)
{
	int f = 0;
	for (int i = a->n2; i >= 0; i--)
	{
		if (f)
			printf("%05d", a->a[i]);
		else if (a->a[i]) {
			printf("%d", a->a[i]);
			f = 1;
		}
	}
}

int solve1(int n) {

	struct LargeInt a = { 0,1,1 };
	struct LargeInt b = { 0,0,0 };
	for (int i = 1; i < 350000; i++) {
		product_ten(&a);
		if (li_mod(&a, n, &b) == 0) {
			li_dump(&b);
			printf(" %d\n", a.n);
			return a.n;
		}
	}
	return 0;
}

int solve()
{
	int x = 1, s;
	int m = 1;
	scanf("%d", &s);
	while (x < s)
	{
		x = x * 10 + 1;
		m++;
	}
	while (1)
	{
		if (x % s == 0) { 
			printf("%d %d\n", x / s, m);
			break; 
		}
		else
		{
			printf("%d", x / s);
			x = x % s;
			x = x * 10 + 1;
			m++;
		}
	}
	return m;
}

int main()
{
	freopen("D:/Develop/GitRepos/MOOC/浙江大学/数据结构/201906/DataStructure/M2019秋C入门和进阶练习集/7-42.txt", "r", stdin);
	solve();
	return 0;
}

